//
//  Solution.h
//  leetcode
//
//  Created by Ellie on 2021/1/21.
//  Copyright © 2021 Ellie. All rights reserved.
//

#ifndef Solution_h
#define Solution_h

#include "DataDefine.h"
#include <queue>
#include <unordered_map>
#include <string>
#include <stack>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        return nullptr;
    }
    
    int minDepth(TreeNode* root)
    {
        if(root == nullptr)
            return 0;
        if(root->left == nullptr && root->right == nullptr)
            return 1;
        int left = minDepth(root->left);
        int right = minDepth(root->right);
        
        if(root->left == nullptr || root-right == nullptr)
            return left + right + 1;
        
        return min(left, right) + 1;
    }
    
    int maxDepth(TreeNode* root)
    {
        if(root == nullptr)
            return  0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return max(left, right) + 1;
    }
    
    // build graph
    // Start from target find level K's Nodes
    unordered_map<TreeNode*, TreeNode*> map_node_parent;
    unordered_map<TreeNode*, int> map_has_visited;
    // root is target
    void distanceK(TreeNode* root, TreeNode* originroot, int K , vector<int> &result)
    {
        if(root == nullptr)
            return;
        inorder(originroot, nullptr, map_node_parent);
        
        queue<TreeNode*> qu;
        qu.push(root);
        int level = 0;
        while(!qu.empty())
        {
            if(level == K + 1)
                return;
            int size = qu.size();
            for(int i=0;i<size;i++)
            {
                TreeNode* cur = qu.front();
                qu.pop();
                if(level == K)
                {
                    result.push_back(cur->val);
                }
                if(cur->left != nullptr && map_has_visited[cur->left] == 0)
                {
                    qu.push(cur->left);
                    map_has_visited[cur->left] = 1;
                }
                if(cur->right != nullptr && map_has_visited[cur->right] == 0)
                {
                    qu.push(cur->right);
                    map_has_visited[cur->right] = 1;
                }
                // push parent
                TreeNode* parent = map_node_parent[cur];
                if(parent != nullptr && map_has_visited[cur] == 0)
                {
                    qu.push(parent);
                    map_has_visited[cur] = 1;
                }
            }
            level ++;
        }
    }
    
    void inorder(TreeNode* root, TreeNode* parent, unordered_map<TreeNode*, TreeNode*> &result)
    {
        if(root == nullptr)
            return;
        result[root] = parent;
        
        cout << "[" << root->val << "," << (result[root] == nullptr ? "null" : to_string(result[root]->val)) << "]" << endl;
        
        inorder(root->left, root, result);
        inorder(root->right, root, result);
    }
    
    vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
        vector<int> result;
        distanceK(target, root,  K, result);
        return result;
    }
    
    string markNULL =  "null";
    char SEP = ' ';
    // serialize and deserialize tree
    // pre-order
    string serialize(TreeNode* root)
    {
        if(root == nullptr)
            return (markNULL + SEP);
        string strvalue = to_string(root->val);
        return strvalue + SEP + serialize(root->left) + serialize(root->right);
    }
    
    TreeNode* deserializeTree(string& input)
    {
        stringstream strstream(input);
        return deserializeTree(strstream);
    }
    
    TreeNode* deserializeTree(stringstream &strstream)
    {
        string str;
        if(!(strstream >> str) || str == markNULL)
        {
            return nullptr;
        }
        int value= stoi(str);
        TreeNode* root = new TreeNode(value);
        root->left = deserializeTree(strstream);
        root->right = deserializeTree(strstream);
        return root;
    }
    
    vector<int> intResult;
    void getallPathNodes(TreeNode* root, vector<vector<int>> &result)
    {
        if(root == nullptr)
            return;
        intResult.push_back(root->val);
        if(root->left == nullptr && root->right == nullptr)
        {
            result.push_back(intResult);
        }
        getallPathNodes(root->left, result);
        getallPathNodes(root->right, result);
        intResult.pop_back();
    }
    
protected:
    void getallPathNodeString(TreeNode* root, vector<string> &result, string path)
    {
        if(root == nullptr)
            return;
        path += to_string(root->val);
        if(root->left == nullptr && root->right == nullptr)
        {
            result.push_back(path);
            return;
        }
        getallPathNodeString(root->left, result, path + "->");
        getallPathNodeString(root->right, result, path + "->");
    }
    
public:
    void getallPathNodesString(TreeNode* root, vector<string> &result)
    {
        getallPathNodeString(root, result, "");
    }
    
    unordered_map<string, int> duplicatestringmap;
    string getmarkPathString(TreeNode* root, vector<string>& result, vector<TreeNode*>& noderesult)
    {
        if(root == nullptr)
            return "#";
        string markleft = getmarkPathString(root->left, result, noderesult);
        string markright = getmarkPathString(root->right, result, noderesult);
        string str =  to_string(root->val) + "#" + markleft + markright;
        result.push_back(str);
        
        if(duplicatestringmap[str] == 1)
        {
            noderesult.push_back(root);
        }
        duplicatestringmap[str] ++;
        return str;
    }
    
    // 1028. 从先序遍历还原二叉树 经典前序遍历的使用
    // 树的左右视图。，通过level实现
    // "1-2--3--4-5--6--7"
    // level-value
    // root level is 0
    // 节点的值大于1
    // 中序遍历同时记录level的反向操作
    string getstringTreewithlevel(TreeNode* root, int level)
    {
        if(root == nullptr)
            return "";
        
        string prefix = "";
        for(int i=0;i<level;i++)
        {
            prefix += "-";
        }
        string str = prefix + to_string(root->val);
        string strleft = getstringTreewithlevel(root->left, level + 1);
        string strright = getstringTreewithlevel(root->right, level + 1);
        return str + strleft + strright;
    }
    
    TreeNode* recoverFromPreorderlevel(int level, queue<int>& levelqueue, queue<int>& valuequeue)
    {
        if(levelqueue.front() != level)
            return nullptr;
        TreeNode* root = new TreeNode(valuequeue.front());
        levelqueue.pop();
        valuequeue.pop();
        root->left = recoverFromPreorderlevel(level + 1, levelqueue, valuequeue);
        root->right = recoverFromPreorderlevel(level + 1, levelqueue, valuequeue);
        return root;
    }
    
    TreeNode* recoverFromPreorder(string S)
    {
        queue<int> levelqueue;
        queue<int> valuequeue;
        int left = 0;
        // getallvaluehelper(input, levelqueue, valuequeue);
        for(int i=0;i<S.size();i++){
            if(S[i]!='-'){
                levelqueue.push(i-left);
                left = i;
                while(i<S.size() && S[i]!='-') i++;
                valuequeue.push(stoi(S.substr(left,i-left)));
                left = i;
            }
        }
        return recoverFromPreorderlevel(0, levelqueue, valuequeue);
    }
    
    // 652. 寻找重复的子树
    // 二叉树的序列化
    vector<TreeNode*> findDuplicateSubTree(TreeNode* root)
    {
        vector<TreeNode*> result;
        vector<string> stringresult;
        getmarkPathString(root, stringresult, result);
        return result;
    }
    
    bool isSubTree(TreeNode* p, TreeNode* q)
    {
        if(p == nullptr)
            return  false;
        return isSameTree(p, q) || isSubTree(p->left, q->left) || isSubTree(p->right, q->right);
    }
    
    bool isSameTree(TreeNode* p, TreeNode* q)
    {
        if(p == nullptr && q == nullptr)
            return true;
        if(p == nullptr || q == nullptr)
            return false;
        
        return (p->val == q->val) && isSameTree(p->left, q->right) && isSameTree(p->right, q->right);
    }
    
    string tree2str(TreeNode* root)
    {
        if(root == nullptr)
            return "";
        if(root->left == nullptr && root->right == nullptr)
            return to_string(root->val);
        if(root->right == nullptr)
            return to_string(root->val) + "(" + tree2str(root->left) + ")";
        return to_string(root->val) + "(" + tree2str(root->left) + ")(" + tree2str(root->right) + ")";
    }
    
    // level-order find most right nodes
    // pre-order[root,right,left]
    
    void rightslideview(TreeNode* root, int level, vector<int>& result)
    {
        if(root == nullptr)
            return;
        // 同一个level出现的第一个元素为该level前序遍历的第一个元素
        if(result.size() < level)
            result.push_back(root->val);
        rightslideview(root->right, level + 1, result);
        rightslideview(root->left, level + 1, result);
    }
    
    void levelorderwithpreorder(TreeNode* root, int level, vector<vector<int>> &result)
    {
        if(root == nullptr)
            return;
        if(result.size() < level)
            result.push_back(vector<int>());
        result[level - 1].push_back(root->val);
        levelorderwithpreorder(root->right, level + 1, result);
        levelorderwithpreorder(root->left, level + 1, result);
    }
    
    // 95. 不同的二叉搜索树 II
    // 1...n为节点的二叉搜索树
    // 96. DP
    // left - right
    
    int numfoBSTrees(int n)
    {
        vector<int> dp = vector<int>(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++)
        {
            for(int j=0;j < i; j++)
            {
                dp[i] += dp[j] * dp[i - 1 - j];
            }
        }
        return dp[n];
    }
    
    // 1-N创建搜索二叉树，中序唯一确定，不用保存中序可以直接在前序中获取
    vector<TreeNode*> generateTrees(int left, int right)
    {
        vector<TreeNode*> result;
        if(left > right)
        {
            result.push_back(nullptr);
            return result;
        }
        for(int i = left; i<= right;i++)
        {
            // left * right = count
            vector<TreeNode*> leftnodes = generateTrees(left, i - 1);
            vector<TreeNode*> rightnodes = generateTrees(i + 1, right);
            
            for(TreeNode* leftnode : leftnodes)
            {
                for(TreeNode* rightnode : rightnodes)
                {
                    // create root with left and right
                    TreeNode* root = new TreeNode(i);
                    root->left = leftnode;
                    root->right = rightnode;
                    
                    result.push_back(root);
                }
            }
        }
        
        return result;
    }
    
    vector<TreeNode*> generateTrees(int n) {
        if( n == 0)
            return vector<TreeNode*>();
        else
            return generateTrees(1, n);
    }
    
    unordered_map<int, int> inordermap;
    
    // build trees with [post-order and in-order]
    // 最关键的计算每次输入的区间，计算子树的node数量可以确定起始和结束
    TreeNode* buildtreepostandinorder(vector<int>& inorder, vector<int>& postorder)
    {
        int size = inorder.size();
        for(int i=0;i<size;i++)
        {
            inordermap[inorder[i]] = i;
        }
        return buildtree_post_inorder(postorder, inorder, size - 1, 0, size - 1);
    }
    
    
    TreeNode* buildtree_post_inorder(vector<int>& postorder, vector<int>& inorder, int rootindex, int left, int right)
    {
        if(left > right)
        {
            return nullptr;
        }
        int rootvalue = postorder[rootindex];
        int rootindexinorder = inordermap[rootvalue];
        int rightnodecount = right - rootindexinorder;
        
        int rightrootindex = rootindex - 1;
        int leftrootindex = rootindex - rightnodecount - 1;
        
        TreeNode* root = new TreeNode(rootvalue);
        
        root->left  = buildtree_post_inorder(postorder, inorder, leftrootindex, 0, rootindexinorder - 1);
        root->right = buildtree_post_inorder(postorder, inorder, rightrootindex, rootindexinorder + 1, right);
        
        return root;
    }
    
    TreeNode* buildtreepreandinorder(vector<int>& inorder, vector<int>& preoder)
    {
        return nullptr;
    }
    
    TreeNode* buildtree_pre_inorder(vector<int>& preorder, vector<int>& inorder, int rootindex, int left, int right)
    {
        return nullptr;
    }
};

#endif /* Solution_h */
